#include "linearList.h"
#include <iostream>
using namespace std;

// 初始化顺序表
sequenceList::sequenceList(const int& cap, const int& len, float arr[])
{
    curNumberOfItem = len;
    maxCapcity = cap;
    myList = new float[maxCapcity];
    for (int i = 0; i < len; i++) {
         myList[i] = arr[i];
     }
}

 // 销毁顺序表
sequenceList::~sequenceList() {
    delete[] myList;
    }

// 添加元素到顺序表尾部
bool sequenceList::addItem(const float& item) {
    if (curNumberOfItem >= maxCapcity) {
        return false;  // 容量不足
     }
    myList[curNumberOfItem++] = item;
    return true;
    }

// 插入元素到指定位置
bool sequenceList::insertItem(const int& index, const float& item) {
    if (index < 0 || index > curNumberOfItem || curNumberOfItem >= maxCapcity) {
        return false;
    }
     for (int i = curNumberOfItem; i > index; i--) {
        myList[i] = myList[i - 1];
    }
    myList[index] = item;
    curNumberOfItem++;
    return true;
    }

 // 删除指定元素，返回删除位置，找不到返回-1
int sequenceList::deleteItem(const float& item) 
{
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == item) {
            for (int j = i; j < curNumberOfItem - 1; j++) {
                myList[j] = myList[j + 1];
            }
            curNumberOfItem--;
            return i;  // 返回删除的位置
        }
    }
    return -1;  // 找不到元素
}

 // 按序号查找元素，返回值并存入val
bool sequenceList::locate(const int& index, float& val) {
    if (index < 0 || index >= curNumberOfItem) {
        return false;  // 序号越界
    }
    val = myList[index];
    return true;
}

// 按值查找元素，返回位置，找不到返回-1
int sequenceList::locate(const float& item) {
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == item) {
            return i;
        }
    }
    return -1;  // 找不到
}

// 倒序排列顺序表中的元素
void sequenceList::reverse() {
    for (int i = 0; i < curNumberOfItem / 2; i++) {
        swap(myList[i], myList[curNumberOfItem - i - 1]);
     }
}

//打印顺序表
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

// 带参数的构造函数，初始化节点数据并设定next指针
listNode::listNode(float nodeData, listNode* succ) {
    data = nodeData;
    next = succ;
}

// 析构函数
listNode::~listNode() {}

// 默认构造函数
linkList::linkList() {
    firstNode = new listNode();
    curNode = lastNode = firstNode;
    listSize = 0;
}

// 使用数组初始化链表
linkList::linkList(const int& len, float arr[]) {
    firstNode = new listNode();
    curNode = lastNode = firstNode;
    listSize = 0;
    for (int i = 0; i < len; i++) {
        tailInsertItem(arr[i]);
    }
}

// 销毁链表
linkList::~linkList() {
    listNode* temp;
    while (firstNode != NULL) {
        temp = firstNode;
        firstNode = firstNode->next;
        delete temp;
    }
}

// 头插法
bool linkList::headInsertItem(const float& item) {
    listNode* newNode = new listNode(item, firstNode->next);
    firstNode->next = newNode;
    if (lastNode == firstNode) {
        lastNode = newNode;
    }
    listSize++;
    return true;
}

// 尾插法
bool linkList::tailInsertItem(const float& item) {
    listNode* newNode = new listNode(item, NULL);
    lastNode->next = newNode;
    lastNode = newNode;
    listSize++;
    return true;
}

// 在指定位置插入元素
int linkList::insertItem(const int& index, const float& item) {
    if (index < 0 || index > listSize) {
        return -1;  // 索引无效
    }
    listNode* prevNode = firstNode;
    for (int i = 0; i < index; i++) {
        prevNode = prevNode->next;
    }
    listNode* newNode = new listNode(item, prevNode->next);
    prevNode->next = newNode;
    if (newNode->next == NULL) {
        lastNode = newNode;
    }
    listSize++;
    return index;
}

// 按值删除元素
int linkList::deleteItem(const float& item) {
    listNode* prevNode = firstNode;
    listNode* curNode = firstNode->next;
    int pos = 0;
    while (curNode != NULL) {
        if (curNode->data == item) {
            prevNode->next = curNode->next;
            if (curNode == lastNode) {
                lastNode = prevNode;
            }
            delete curNode;
            listSize--;
            return pos;
        }
        prevNode = curNode;
        curNode = curNode->next;
        pos++;
    }
    return -1;  // 未找到
}

// 按位查找元素
bool linkList::locate(const int& index, float& val) {
    if (index < 0 || index >= listSize) {
        return false;  // 索引无效
    }
    listNode* curNode = firstNode->next;
    for (int i = 0; i < index; i++) {
        curNode = curNode->next;
    }
    val = curNode->data;
    return true;
}

// 按值查找元素
int linkList::locate(const float& item) {
    listNode* curNode = firstNode->next;
    int pos = 0;
    while (curNode != NULL) {
        if (curNode->data == item) {
            return pos;
        }
        curNode = curNode->next;
        pos++;
    }
    return -1;  // 未找到
}

// 链表升序排序
void linkList::ascendingOrder() {
    if (firstNode->next == NULL || firstNode->next->next == NULL) {
        return;  // 链表为空或只有一个元素
    }
    for (listNode* i = firstNode->next; i->next != NULL; i = i->next) {
        for (listNode* j = i->next; j != NULL; j = j->next) {
            if (i->data > j->data) {
                std::swap(i->data, j->data);
            }
        }
    }
}

// 链表倒序
void linkList::reverse() {
    if (firstNode->next == NULL || firstNode->next->next == NULL) {
        return;  // 链表为空或只有一个元素
    }
    listNode* prev = NULL;
    listNode* curr = firstNode->next;
    listNode* nextNode = NULL;
    lastNode = curr;
    while (curr != NULL) {
        nextNode = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextNode;
    }
    firstNode->next = prev;
}

//链表打印
void linkList::print()
{
    curNode = firstNode;
    cout << listSize << ":";
    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        curNode = curNode->next;
    }
}

// 合并两个无序链表A和B
void merge(linkList& A, linkList& B) {
    A.ascendingOrder();
    B.ascendingOrder();
    //创建一个新的链表
    linkList mergedList;
    //获取链表A和B的第一个有效节点
    listNode* pA = A.firstNode->next;
    listNode* pB = B.firstNode->next;
    //归并两个链表
    while (pA != NULL && pB != NULL) {
        if (pA->data < pB->data) {
            mergedList.tailInsertItem(pA->data);
            pA = pA->next;
        } else {
            mergedList.tailInsertItem(pB->data);
            pB = pB->next;
        }
    }
    //如果链表A还有剩余节点
    while (pA != NULL) {
        mergedList.tailInsertItem(pA->data);
        pA = pA->next;
    }
    //如果链表B还有剩余节点
    while (pB != NULL) {
        mergedList.tailInsertItem(pB->data);
        pB = pB->next;
    }
    mergedList.reverse();
    A = mergedList;
    B.~linkList();
}
